from typing import *
from math import inf


class Solution:
    def minCostToEqualizeArray(self, nums: List[int], cost1: int, cost2: int) -> int:
        n = len(nums)
        mod = 10**9 + 7
        if n == 1:
            return 0
        mx = max(nums)
        mn = min(nums)
        if n == 2:
            return (mx - mn) * cost1 % mod

        if cost1 * 2 <= cost2:
            return (mx * n - sum(nums)) * cost1 % mod
        sm = sum(nums)
        d = n * mx - sm

        if mx - mn <= (n - 1) * mx - sm + mn:
            if d & 1 == 0:
                return d // 2 * cost2 % mod
            else:
                ans1 = d // 2 * cost2 + cost1
                if (n + 1) & 1 == 0:
                    ans1 = min(d // 2 * cost2 + (n + 1) // 2 * cost2, ans1)
                return ans1 % mod

        H = mx - mn - ((n - 1) * mx - sm + mn)
        cost = (mx - mn - H) * cost2
        ans = cost + H * cost1
        while H >= n - 1:
            H = H - (n - 1) + 1
            cost += (n - 1) * cost2
            ans = min(ans, cost + H * cost1)
        if (n - H) % 2 == 0:
            ans = min(ans, cost + (H + (n - H) // 2) * cost2)
        else:
            ans = min(ans, cost + (H + (n - H) // 2) * cost2 + cost1)
            if (n + 1) & 1 == 0:
                ans = min(ans, cost + (H + (n - H) // 2) * cost2 + (n + 1) // 2 * cost2)
        return ans % mod


class Solution:
    def minCostToEqualizeArray(self, nums: List[int], cost1: int, cost2: int) -> int:
        n = len(nums)
        mod = 10**9 + 7
        if n == 1:
            return 0

        def max(a, b):
            return a if a >= b else b

        def min(a, b):
            return a if a <= b else b

        sm = 0
        mx, mn = 0, inf
        for num in nums:
            mx, mn = max(mx, num), min(mn, num)
            sm += num

        if n == 2:
            return (mx - mn) * cost1 % mod

        if cost1 * 2 <= cost2:
            return (mx * n - sm) * cost1 % mod

        d = n * mx - sm

        if mx - mn <= (n - 1) * mx - sm + mn:
            if d & 1 == 0:
                return d // 2 * cost2 % mod
            else:
                ans1 = d // 2 * cost2 + cost1
                if (n + 1) & 1 == 0:
                    ans1 = min(d // 2 * cost2 + (n + 1) // 2 * cost2, ans1)
                return ans1 % mod

        H = mx - mn - ((n - 1) * mx - sm + mn)
        cost = (mx - mn - H) * cost2
        ans = cost + H * cost1
        while H >= n - 1:
            H = H - (n - 1) + 1
            cost += (n - 1) * cost2
            ans = min(ans, cost + H * cost1)
        if (n - H) % 2 == 0:
            ans = min(ans, cost + (H + (n - H) // 2) * cost2)
        else:
            ans = min(ans, cost + (H + (n - H) // 2) * cost2 + cost1)
            if (n + 1) & 1 == 0:
                ans = min(ans, cost + (H + (n - H) // 2) * cost2 + (n + 1) // 2 * cost2)
        return ans % mod


s = Solution()
print(s.minCostToEqualizeArray([60, 19, 53, 31, 57], 60, 2))
# print(s.minCostToEqualizeArray([4, 1], 5, 2))
